package com.cqs.leetcode.dp;

import com.cqs.leetcode.ds.ArraysUtils;

import java.util.ArrayList;
import java.util.List;

/**
 * lixw
 * 2021/11/9
 **/
public class MaximumSumCircularSubarray918 {

    //leetcode 简洁写法
    public int maxSubarraySumCircular2(int[] nums) {
        int dp = nums[0],max = dp, sum = dp,min = 0;
        for(int i = 1; i < nums.length; i++){
            sum += nums[i];
            dp = nums[i] + Math.max(dp, 0);
            max = Math.max(dp, max);
        }
        dp = nums[0];
        for(int i = 1; i < nums.length -1; i++){
            dp = nums[i] + Math.min(0,dp);
            min = Math.min(dp,min);
        }
        return Math.max(sum-min,max);
    }


    public int maxSubarraySumCircular(int[] nums) {
        //无环的请求
        int max = nums[0];
        if (nums.length == 1) return max;
        int cur = nums[0];
        //无环的情况 --XXXXX---格式
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], nums[i] + cur);
            max = Math.max(cur, max);
        }

        //求最小值的
        int curMin = nums[0];
        int min = nums[0];
        int sum = nums[0];
        int maxEle = nums[0]; //最大的元素
        //处理包含两头XXXX----XXXXX的格式
        for (int i = 1; i < nums.length; i++) {
            curMin = Math.min(nums[i], nums[i] + curMin);
            sum += nums[i];
            maxEle = Math.max(nums[i], maxEle);
            min = Math.min(curMin, min);
        }

        if (maxEle <= 0) {
            return maxEle;
        }

        //排除所有的值均是-1的情况
        return Math.max(max, sum - min);
    }


    public static void main(String[] args) {
        MaximumSumCircularSubarray918 m = new MaximumSumCircularSubarray918();
        List<int[]> cases = new ArrayList<>();
        cases.add(new int[]{-3, -5, -2, -5, -6}); //-2
        cases.add(new int[]{-2, 4, -5, 4, -5, 9, 4}); //15
        cases.add(new int[]{5, -3, 5}); // 10
        cases.add(new int[]{1, -2, 3, -2}); //
        cases.add(new int[]{2, -2, 2, 7, 8, 0});
        cases.add(new int[]{5, 4, 4});
        cases.add(new int[]{5, 4, -1});
        cases.add(new int[]{1, 2, 3});
        cases.add(new int[]{-3, 2, 3});
        for (int[] t : cases) {
            System.out.println(ArraysUtils.formatInts(t) + "--->" + m.maxSubarraySumCircular(t));
        }
    }

}
